Precomputation in the data transmission context refers generally to the process of computing a set of end-to-end routes through a network prior to the arrival of data transmission requests. A route is also commonly referred to as a path, and the terms are typically used interchangeably. When a new request arrives, the particular route that best matches the bandwidth requirements of the request is chosen from the precomputed set. This “offline” routing process is in contrast to “online” routing, also known as on-demand routing, where routes are computed upon the arrival of the corresponding requests.
Conventional precomputation techniques are generally based on the same hop-minimization algorithms that are commonly used in online routing. These include shortest-path algorithms such as the Dijkstra algorithm described in E. W. Dijkstra, “A Note on Two Problems in Connection with Graphs,” Numerische Mathematik 1, pp. 269-271, 1959, and the K-shortest path (KSP) algorithm described in E. L. Lawler, “A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and its Application to the Shortest Path Problem,” Management Science, Vol. 18, pp. 401405, March 1972. An extension of shortest-path known as widest-shortest path is described in R. Guerin et al., “QoS Routing Mechanisms and OSPF Extensions,” Proc. of Globecom 1997. Another precomputation approach involves choosing routes which are as diverse as possible, for example, vertex or edge disjoint, and have the lowest total cost. This approach is referred to as the K-best paths algorithm, and is described in S.-W. Lee et al., “A K-best paths algorithm for highly reliable communication networks,” IEICE Trans. Communications, 1999, and S. D. Nikolopoulos et al., “Addressing Network Survivability Issues by Finding the K-best Paths Through a Trellis Graph,” Proc. of IEEE Infocom, 1997.
A number of techniques have also been developed which attempt to reduce the storage and computational complexity of the precomputation process. These techniques are generally directed to lowering the cost of computing hop-minimization routes. For example, an enhancement to the Dijkstra algorithm to permit computation of multiple equal-cost routes for each destination is described in A. Shaikh et al., “Efficient Precomputation of Quality-of-Service Routes,” Proc. Workshop on Network and Operating Systems Support for Digital Audio and Video, pp. 15-27, July 1998. A variation of a Bellman-Ford algorithm suitable for use in precomputing routes for different hop counts is described in A. Orda et al., “QoS Routing: The Precomputation Perspective,” Proc. of IEEE Infocom, 1999. Techniques for determining which specific routes to cache in order to lower storage overhead is described in M. Peyravian et al., “Network Path Caching: Issues, Algorithms and a Simulation Study,” Computer Communications, 20(8), pp. 605-614, August 1997.
A significant problem with conventional precomputation techniques such as those mentioned above is that these techniques are based upon an assumption that the hop-minimization algorithms that provide acceptable performance in online routing are equally valid in the precomputation setting. However, the use of hop-minimization algorithms for precomputation can increase network bottlenecks or otherwise lead to poor routing decisions, thereby reducing network capacity utilization, particularly for applications involving bandwidth guaranteed traffic.
Other algorithms have been developed which attempt to avoid the above-described bottleneck problem associated with hop-minimization approaches. Examples of such algorithms include the MIRA algorithm and modified MIRA algorithm as described in M. Kodialam et al, “Minimum Interference Routing with Applications to MPLS Traffic Engineering,” Proc. of IEEE Infocom, 2000, and S. Suri et al. “Profile-Based Routing: A New Frame work for MPLS Traffic Engineering,” Proc. of QofIS, 2001, respectively. However, these techniques have a number of drawbacks that limit their applicability in general and for precomputation in particular. For example, these techniques generally rely on avoiding specific links in a network, but this approach is counterproductive for precomputation. More specifically, precomputing routes on a network that is weighted to discourage use of specific links can lead to poor network utilization since many of these links may never feature in any of the materialized routes. This can impose serious penalties in precomputation.
A need therefore exists for an improved route precomputation approach which can avoid the bottleneck and network utilization problems associated with hop-minimization algorithms while also providing higher quality routes and enhanced efficiency relative to the above-described conventional techniques.